Computer systems such as personal computers and stand-alone video games are commonly used for displaying graphical objects on a display screen. These graphical objects include points, lines, polygons, and three dimensional objects. By utilizing texture mapping techniques, color and other details can be applied to areas and surfaces of graphical objects. In texture mapping, a pattern image, also referred to as a "texture map," is combined with an area or surface of an object to produce a modified object with the added texture detail. For example, given the outline of a featureless cube and a texture map defining a wood grain pattern, texture mapping techniques can be used to "map" the wood grain pattern onto the cube. The resulting display is that of a cube that appears to be made of wood. In another example, vegetation and trees can be added by texture mapping onto an otherwise barren terrain model. Likewise, labels can be applied onto packages or cans for visually conveying the appearance of an actual product. Textures mapped onto geometric surfaces provide motion and spatial cues that surface shading alone might not provide. For example, a sphere rotating about its center appears static until an irregular texture or pattern is affixed to its surface.
The resolution of a texture varies, depending on the viewpoint of the observer. For example, the texture of a block of wood displayed up-close has a different appearance than if that same block of wood were to be displayed far away. Consequently, there needs to be some method for varying the resolution of the texture. One available approach is to compute the variances of texture in real time, but this is usually too slow for complex textures or requires expensive hardware to implement.
A more practical approach creates and stores a MIP-map (Multum In Parvo meaning "many things in a small place"). The MIP-map comprises a texture pattern pre-filtered at progressively lower or coarser resolutions and stored at varying levels of detail (LOD) in the form of maps. See, e.g., the explanation of conventional texture MIP-mapping in Foley et al., Computer Graphics Principles and Practice, Second Edition, Addison-Wesley Publishing Company, Reading, Mass. (1992), pages 741-44 and 826-828 (incorporated herein by reference).
FIG. 1A shows a conventional set of texture LOD maps having pre-filtered texel data associated with a particular texture. Four different levels of detail (LOD[O]-LOD[3]) are shown. Each successively coarser texture LOD has a resolution half that of the preceding LOD in each dimension until a unitary LOD is reached representing an average of the entire high resolution base texture map. Thus, in FIG. 1A, LOD[0] is a high resolution 8.times.8 texel array; LOD[1] is a 4.times.4 texel array; LOD[2] is a 2.times.2 texel array; and LOD [3] is a single 1.times.1 texel array. Of course, in practice each LOD can contain many more texels, for instance, LOD[0] can be 8k.times.8k, LOD[1] 4k.times.4k, and so forth depending upon the particular hardware or processing limits encountered.
The benefit of MIP-mapping is that variance calculation, or filtering, is only performed once on texel data when the MIP-map is initially created and stored in a plurality of LOD maps. Thereafter, texels commensurate with pixel size are obtained by selecting the closest LOD map having an appropriate resolution. By obtaining texels from the pre-filtered LOD maps, filtering does not have to be performed during run-time, and more sophisticated filtering operations can be executed during preliminary modeling without delaying real-time operation speed.
To render a display at the appropriate image resolution, a texture LOD is selected based on the relationship between the smallest texel dimension and the display pixel size. For a perspective view of a landscape 100, as shown in FIG. 1B, the displayed polygonal image is "magnified" in a foreground region relative to polygonal regions located closer to the center horizon and background along the direction indicated by the arrow. To provide texture for pixels in the closest foreground region, texels are retrieved from the finest resolution map LOD[0]. Appropriate coarser LODs are used for texel data covering pixels located further away from the viewer's eyepoint. Such multi-resolution texture MIP-mapping ensures that texels of the appropriate texture LOD get selected during pixel sampling. To avoid discontinuities between images at varying resolutions, well-known techniques such as linear interpolation are used to blend the texel values of two LODs nearest a particular pixel's resolution.
A significant drawback of conventional MIP-mapping, however, is the speed with which the data stored in the maps can be retrieved. For example, main memory in the form of a dynamic random access memory (DRAM) or a static random access memory (SRAM) is an expensive, somewhat slow, and inefficient site for a large texture MIP-map. The problem is exacerbated by the fact that each higher level of detail map requires four times more memory than the next smaller map. For example, a 16.times.16 texture array having 256 texture picture elements (texels), is four times bigger than an 8.times.8 texture array which has 64 texels. To put this increase in perspective, a texture MIP-map having six levels of detail requires over 4,096 times more memory than the texture map at the coarsest resolution found in the MIP-map. Implementing and accessing large texture MIP-maps quickly becomes an expensive and challenging luxury. In addition, for large texture MIP-maps, many portions of the stored MIP-map are not used in a display image, resulting in wasted space and unnecessarily slowed access time.
Thus, there is a need to efficiently access large texture data maps for display purposes so as to minimize attendant data retrieval delay and costs. Final images in an improved texture data accessing system are preferably indistinguishable from or an improvement upon those accessed using a traditional approach.
One approach found in industry is the use of a high speed cache dedicated to the storage of texture data. However, available caching techniques are less than satisfactory for an industry focussed on keeping data access and processing speed to a maximum and cost to a minimum. For example, an available "most recent four" texel cache stores the last four texels requested in an easily accessed format, but for only one pixel over a plurality of clock cycles. Larger texel caches that service a plurality of texels for each pixel in each clock cycle may also be combined to form a cache array. However, such brute force approaches can be quite expensive to implement in silicon. Similarly, the use of multiple, independent memories, each storing aligned texels, is only effective when all active textures are stored in cache, again aggravating cost and silicon real estate concerns.
There is therefore a need in the art of texture data manipulation for a wide bandwidth caching scheme that accommodates increasing graphics processing system speeds without monopolizing considerably more silicon real estate than is currently dedicated to the texture data storage and access tasks.